# """
# This is Sea's API interface.
# You should not implement it, or speculate about its implementation
# """
class Sea(object):
    def hasShips(self, topRight: 'Point', bottomLeft: 'Point') -> bool:
        pass


class Point(object):
    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y


class Solution(object):
    def countShips(self, sea: 'Sea', topRight: 'Point', bottomLeft: 'Point') -> int:
        if sea.hasShips(topRight, bottomLeft):
            x1, y1 = bottomLeft.x, bottomLeft.y
            x2, y2 = topRight.x, topRight.y

            if x1 == x2 and y1 == y2:
                return 1

            # 水平切割
            if x2 - x2 >= y2 - y1:
                x3 = (x1 + x2) // 2
                x4 = x3 + 1
                return (self.countShips(sea, Point(x3, y2), Point(x1, y1)) +
                        self.countShips(sea, Point(x2, y2), Point(x4, y1)))

            # 垂直切割
            else:
                y3 = (y1 + y2) // 2
                y4 = y3 + 1
                return (self.countShips(sea, Point(x2, y3), Point(x1, y1)) +
                        self.countShips(sea, Point(x2, y2), Point(x1, y4)))
        else:
            return 0


if __name__ == "__main__":
    pass
